/**
 * 33. 搜索旋转排序数组
 */
public class Solution_33 {
    /**
     * 方法二：二分查找
     * <p>
     * 将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的
     * <p>
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     */
    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        if (len == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int left = 0, right = len - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 如果 target == nums[mid]
            if (nums[mid] == target) {
                return mid;
            }
            // 将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的
            /**
             * 如果 [left, mid - 1] 是有序数组，且 target 的大小满足 [nums[left], nums[mid])，
             * 则我们应该将搜索范围缩小至 [left, mid - 1]，否则在 [mid + 1, right] 中寻找。
             */
            if (nums[0] <= nums[mid]) {
                if (target >= nums[0] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            /**
             * 如果 [mid, right] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，
             * 则我们应该将搜索范围缩小至 [mid + 1, right]，否则在 [left, mid - 1] 中寻找。
             */
            else {
                if (target > nums[mid] && target <= nums[nums.length - 1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 方法一：线性扫描
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     */
    public int search1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution_33 solution = new Solution_33();
        int[] nums = { 4, 5, 6, 7, 0, 1, 2 };
        int target = 0;
        int ans = solution.search(nums, target);
        System.out.println(ans);
    }
}
